/**560. 和为 K 的子数组
 * - 给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。
 * - 子数组是数组中元素的连续非空序列。
 * - https://leetcode.cn/problems/subarray-sum-equals-k/description/
 */
function subarraySum(nums: number[], k: number): number {
    // 我们需要找到和为k的连续子数组的个数。
    // 通过计算前缀和，我们可以将问题转化为求解两个前缀和之差等于k的情况。
    // 假设数组的前缀和数组为 prefixSum，其中prefixSum[i]表示【从数组起始位置 到 第i个位置 的元素之和】
    // 那么对于任意的两个下标i和j（i < j），如果prefixSum[j] - prefixSum[i] = k，
    // 即从第i个位置到第j个位置的元素之和等于k，那么说明从第i+1个位置到第j个位置的连续子数组的和为k。

    // 通过遍历数组，计算每个位置的前缀和，并使用一个哈希表来存储每个前缀和出现的次数。
    // 在遍历的过程中，我们检查是否存在prefixSum[j] - k的前缀和，如果存在，说明从某个位置到当前位置的连续子数组的和为k，我们将对应的次数累加到结果中。
    // 这样，通过遍历一次数组，我们可以统计出和为k的连续子数组的个数，并且时间复杂度为O(n)，其中n为数组的长度。


    const map = new Map<number, number>([[0, 1]])//初始化(0,1)，代表当前前缀和为0的次数为1
    let count = 0
    let preSum = 0
    for (let i = 0; i < nums.length; i++) {
        preSum += nums[i] //计算当前前缀和
        if (map.has(preSum - k)) {
            //如果前缀和减k，在map中有记录，说明某个位置到当前位置i的和为k，就可以count加上map中记录的数据了
            count += map.get(preSum - k)!
        }
        //然后需要记录当前前缀和的map，已有的加一，没有的初始化为1 
        map.set(preSum, (map.get(preSum) || 0) + 1)
    }
    return count
}